package com.mdnote.practice.linked_list;

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/9
 * @description 环形链表
 */
public class LeetCode141 {

    public boolean hasCycle(ListNode head) {
//        return double_cursor(head);

        return hashtable(head);
    }

    private boolean hashtable(ListNode head) {

        HashSet<ListNode> visited = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (!visited.add(cur)) {
                return true;
            }
            cur = cur.next;
        }

        return false;
    }

    private boolean double_cursor(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head, fast =head.next;
        while (fast != null && fast.next != null && fast.next.next != null) {
            // System.out.println("slow:" + slow.val + " fast:" + fast.val);
            if (fast == slow) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return false;
    }

    private static class ListNode {
          int val;
          ListNode next;
          ListNode(int x) {
              val = x;
              next = null;
          }
      }
}
